package il.ac.bgu.cs.heuristics.core;

import il.ac.bgu.cs.heuristics.graph.State;
import il.ac.bgu.cs.heuristics.graph.types.ContradictingStatesException;
import il.ac.bgu.cs.heuristics.graph.types.IAction;
import il.ac.bgu.cs.heuristics.graph.types.IActionGraph;
import il.ac.bgu.cs.heuristics.graph.types.IPath;
import il.ac.bgu.cs.heuristics.graph.types.IState;
import il.ac.bgu.cs.heuristics.graph.types.ISubstitution;
import il.ac.bgu.cs.heuristics.utils.CollectionUtils;
import il.ac.bgu.cs.heuristics.utils.Pair;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.jgraph.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

/**
 * @author haro
 * 
 */
public class HeuristicEngineComplex extends heuristicsEngine {

	private Set<Pair<IState>>	set	= null;

	public HeuristicEngineComplex(IActionGraph aGraph) {
		super(aGraph);
	}

	/**
	 * @param init
	 * @param goal
	 * @return the heuristic value for this init to reach the goal
	 */
	@Override
	public int getHValue(IState init, IState goal) {
		int hvalue = 0;
		Stack<IAction> actionsStack = new Stack<IAction>();
		ArrayList<IAction> actionsList = new ArrayList<IAction>();
		set = CollectionUtils.newLinkedHashSet();
		int value = extractHeuristic(init.clone(), goal.clone(), hvalue,
				actionsStack, actionsList);
		return value;
	}

	/**
	 * @param init
	 * @param goal
	 * @param hvalue
	 * @param actionsStack
	 * @param actionsList
	 * @return h value, this is the recursive call for the algorithm
	 */
	private int extractHeuristic(IState init, IState goal, int hvalue,
			Stack<IAction> actionsStack, ArrayList<IAction> actionsList) {
		log("==========================================================");
		log("new call: \n init is: \n: " + init.toString() + "\ngoal is: \n"
				+ goal.toString());
		if (!set.add(new Pair<IState>(init, goal)))
			throw new SameInitGoalPairException(init, goal, hvalue, set.size());

		if (init.contains(goal)) {// we are not looking for equal since goal can
			// be not a full state
			return returnHValue(hvalue);// we reached our goal , we are done
		}
		Set<IState> notFilteredgoalsInAG = aGraph
				.getNonContradictingEffects(goal);// 2
		Set<IState> goalsInAG = filterGoals(init, goal, notFilteredgoalsInAG,
				new AlreadyInInitFilter(), new NotUsefulGoalsStateFilter());

		// filterGoals(init, goalsInAG);// 3
		log("goals after filter: \n" + goalsInAG.toString());

		// 4
		if (goalsInAG.isEmpty()) {
			RegressionOutcome outcome = regressGoal(init, goal, actionsStack);
			if (!outcome.isRegressed)// we could not find a
			// goal we can regress
			{
				return returnHValue(hvalue);
			} else {
				return extractHeuristic(outcome.mInit, outcome.mGoal, hvalue,
						actionsStack, actionsList);
			}
			// notice here init and goal have changed because of regress goal
			// method
		}

		aGraph.setInitState(init.clone());

		// 5
		// the consistent graph is made of the pairs of extended goal along with
		// the path to the original goal
		Map<IState, IPath> consistentGoalsAndPath = getConsistentGoals(init,
				goalsInAG);
		if (consistentGoalsAndPath.isEmpty()) {
			IPath shortestPath = getShortestGivenList(init, goalsInAG);
			IState subgoal = State.createState(shortestPath.getConstraints());
			log("no consistent goal \n" + shortestPath.toString()
					+ "\n new subgoal: " + subgoal.toString());
			// we send the recursion to change init to the subgoal
			int hvalueSubgoal = extractHeuristic(init, subgoal, hvalue,
					actionsStack, actionsList);
			// at this point we assume the subgoal have been reached meaning the
			// init to meet subgoal

			// since we change init using swap thier is not point on doing that
			// IState newInitState = subgoal.mergeAndOverride(init);

			// since the init had change according to a goal given list there is
			// at least one goal where his
			// given list is now consistent with Init.
			return extractHeuristic(init, goal, hvalue + hvalueSubgoal,
					actionsStack, actionsList);
		}

		SimpleGraph<IState, DefaultEdge> constrainGraph = getConstrainGraph(consistentGoalsAndPath);
		Set<IState> maxIS = getMaxIS(constrainGraph);

		Set<IPath> pathsToGoal = getPaths(maxIS, consistentGoalsAndPath);
		IState initDiff = createNewInitState(maxIS);
		initDiff = initDiff.mergeAndOverride(init);

		List<IAction> actionsTaken = CollectionUtils.newArrayList();
		int numberOfActions = 0;
		for (IPath path : pathsToGoal) {
			numberOfActions += path.weight();
			actionsTaken.addAll(path.getActions());
		}

		init.swap(initDiff);
		actionsList.addAll(actionsTaken);
		actionsStack.addAll(actionsTaken);

		return extractHeuristic(init, goal, hvalue + numberOfActions,
				actionsStack, actionsList);
	}

	/**
	 * @param IState
	 *            init
	 * 
	 * @param goalsInAG
	 *            - the set of goals.
	 * 
	 * @return - return IPath representaing the lowest given_list score -
	 *         meaning the amount of proposition in the constraintsList which
	 *         are NOT in Init is the lowest.
	 */
	private IPath getShortestGivenList(IState init, Set<IState> goalsInAG) {
		IPath pathWithLowestScore = null;
		int lowestConstraintsListScore = Integer.MAX_VALUE;
		IPath goalPath = null;
		for (IState goal : goalsInAG) {
			goalPath = aGraph.getShortestPath(init, goal);
			Set<ISubstitution> constraintsList = goalPath.getConstraints();
			int constraintsListScore = constraintsList.size()
					- init.getNumberOfContainedSubstitution(constraintsList);
			if (constraintsListScore <= lowestConstraintsListScore) {
				pathWithLowestScore = goalPath;
				lowestConstraintsListScore = constraintsListScore;
			}
		}
		return pathWithLowestScore;

	}

	/**
	 * @param maxIS
	 *            - the set of goal to be achived in this recursive call
	 * @return - a state representing all the propositision in goal that we will
	 *         achive this recursive call
	 */
	IState createNewInitState(Set<IState> maxIS) {
		IState newInit = State.createState(new HashSet<ISubstitution>());
		for (IState goal : maxIS) {
			try {
				newInit = newInit.merge(goal);
			} catch (ContradictingStatesException e) {
				e.printStackTrace();
			}

		}
		return newInit;
	}

	/**
	 * @param stateSet
	 *            - max IS of the constrain graph
	 * @param statesPaths
	 *            - map each state to his path
	 * @return a union of all the actions in the path from init to all the state
	 *         in state set.
	 */
	private Set<IAction> getActions(Set<IState> stateSet,
			Map<IState, IPath> statesPaths) {
		Set<IAction> actions = CollectionUtils.newLinkedHashSet();
		for (IState state : stateSet) {
			actions.addAll(statesPaths.get(state).getActions());
		}
		return actions;
	}

	private Set<IPath> getPaths(Set<IState> stateSet,
			Map<IState, IPath> statesPaths) {
		Set<IPath> paths = CollectionUtils.newLinkedHashSet();
		for (IState state : stateSet) {
			paths.add(statesPaths.get(state));
		}
		return paths;
	}

	/**
	 * @param graph
	 *            the constrainGraph - an edge exist between v1 and v2 iff they
	 *            cannot be merged
	 * @return a set of the max independet set of the graph using the greedy
	 *         algorithem
	 */

	private IState[] createExtendedGoalArray(
			Map<IState, IPath> consistentGoalsAndPath) {
		List<IState> extendedGoalsStates = CollectionUtils.newArrayList();
		for (IPath path : consistentGoalsAndPath.values()) {
			extendedGoalsStates.add(path.getExtendedGoalState());
		}
		return extendedGoalsStates.toArray(new IState[0]);
	}

	private IPath getShortestPath(Map<IState, IPath> map) {
		IPath shortestPath = null;
		int size = Integer.MAX_VALUE;
		for (IPath path : map.values()) {
			if (path.getConstraints().size() <= size) {
				size = path.getConstraints().size();
				shortestPath = path;
			}
		}
		assert (shortestPath != null);
		return shortestPath;
	}

	/**
	 * @param init
	 * @param goals
	 *            - set of goals to reach this method filter the goals set to
	 *            remove all the states in goals that already exist in init,
	 *            step 3 of the algorithm
	 */
	protected void filterGoals(IState init, Set<IState> goals) {
		Set<IState> statesToRemove = CollectionUtils.newLinkedHashSet();
		for (IState state : goals) {
			if (init.contains(state)) {
				statesToRemove.add(state);
			}
		}
		goals.removeAll(statesToRemove);
	}

	public class RegressionOutcome {
		public IState	mInit;
		public IState	mGoal;
		public boolean	isRegressed;

		public RegressionOutcome(boolean regressed, IState init, IState goal) {
			mInit = init;
			mGoal = goal;
			isRegressed = regressed;
		}

	}

	/**
	 * @param initState
	 *            - the init state if the method return true this will have the
	 *            regressed init
	 * @param goal
	 *            - same as init.
	 * @param actionsStack
	 *            - we will leave here only action that we didnt reach yet
	 * @return a struct containing the regression outcome , the isReggressed
	 *         field is true iff there is a action in the action stack that if
	 *         we regress it in the goal state context we will reach to a new
	 *         goal state that have goals . notice if we find such a action we
	 *         will regress the init state too.
	 * 
	 *         if isReggressed field is false the other fields in
	 *         RegressionOutcome are null
	 */
	private RegressionOutcome regressGoal(IState initState, IState goal,
			Stack<IAction> actionsStack) {
		IAction actionToRegress;
		while (!actionsStack.isEmpty()) {
			actionToRegress = actionsStack.pop();

			if (Collections.disjoint(actionToRegress.getEffect(), goal
					.getSubstitutions()))// no point to check for regression
				continue;

			IState newGoal = regressState(goal, actionToRegress);
			Set<IState> goalsInAG = aGraph.getNonContradictingEffects(newGoal);
			filterGoals(initState, goalsInAG);
			if (goalsInAG.isEmpty())// we need to check if we find goal Vertexes
				continue;

			IState newInit = regressState(initState, actionToRegress);
			return new RegressionOutcome(true, newInit, newGoal);
		}
		return new RegressionOutcome(false, null, null);
	}

	/**
	 * @param state
	 *            - the state to regress
	 * @param action
	 *            - the action
	 * @return the state after regression using the action = action precondition
	 *         U ( state - action effect )
	 */
	private IState regressState(IState state, IAction action) {
		Set<ISubstitution> actionPrecondition = copySet(action
				.getPreconditions());
		Set<ISubstitution> actionEffect = copySet(action.getEffect());
		Set<ISubstitution> goalSubstitution = copySet(state.getSubstitutions());
		Set<ISubstitution> newState = new HashSet<ISubstitution>(
				actionPrecondition);

		goalSubstitution.removeAll(actionEffect);
		newState.addAll(goalSubstitution);

		return State.createState(newState);

	}

	// TODO should be replaced with a copySet for cloneable
	public Set<ISubstitution> copySet(Set<ISubstitution> set) {
		Set<ISubstitution> newSet = CollectionUtils.newLinkedHashSet();
		for (ISubstitution sub : set) {
			try {
				newSet.add(sub.clone());
			} catch (CloneNotSupportedException e) {
				e.printStackTrace();
			}

		}
		return newSet;
	}

	private int returnHValue(int hvalue) {

		// System.out.println(hvalue);
		return hvalue;
	}

}
